
class Solution {
public:

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = list1, *p2 = list2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};

// 2. 分隔链表
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // 定义两个虚拟头结点
        // 将原链表分成两条短链表, 一者节点值小于x, 一者节点值不小于x
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;

        ListNode* p = head;

        while(p != nullptr)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }

            p = p->next;
        }

        // 节点值不小于x的短链表尾置空
        p2->next = nullptr;

        p1->next = newnode2->next;
        return newnode1->next;
    }
};




// 3. 合并K个有序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义一个最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        // 将K个链表的头结点插入到最小堆中
        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);

            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};


// 4. 链表的倒数第K个节点
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        ListNode* p1 = head, *p2 = head;
        ListNode* p = head;

        // p1先走k步, 此时再走n-k步就走到尾了
        for(int i = 0; i < k; i++)
        {
            if(p1) // 防止越界
                p1 = p1->next;
        }

        // p2从头开始和p1一起走, 直至p1指向尾, p2所在的位置就是答案
        while(p1 != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 5. 删除链表的倒数第K个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 定义一个虚拟头结点, 将头结点插入其后 - 防止头删head节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        // 单链表中删除一个节点需要找到其前一个节点
        // 找单链表中倒数第N个节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head, *p2 = head;
        ListNode* p = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 6. 链表的中间结点
class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};


// 7. 环形链表
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                return true;
        }

        return false;
    }
};



// 8. 环形链表II
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        // slow 从头开始走
        slow = head;

        // slow和fast再次相遇点即为入口点
        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};



// 9. 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        ListNode* p1 = headA, *p2 = headB;

        // p1先遍历链表A再遍历链表B, p2先遍历链表B再遍历链表A
        // 保证二者遍历的链表长度相同
        while(p1 != p2)
        {
            if(p1 == nullptr)
                p1 = headB;
            else
                p1 = p1->next;

            if(p2 == nullptr)
                p2 = headA;
            else
                p2 = p2->next;
        }

        return p1;
    }
};



// 剑指offer - 合并排序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        // 将链表数组插入到最小堆中
        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            p->next = pMin;

            if(pMin->next)
                pq.push(pMin->next);

            p = p->next;
        }

        return newnode->next;
    }
};


// 剑指offer - 两个链表的第一个重合交点
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先遍历链表A再遍历链表B, p2先遍历链表B再遍历链表A
        // 这样就保证了遍历链表的长度相同
        ListNode* p1 = headA, *p2 = headB;

        while(p1 != p2)
        {
            if(p1 == nullptr)
                p1 = headB;
            else
                p1 = p1->next;

            if(p2 == nullptr)
                p2 = headA;
            else
                p2 = p2->next;
        }

        return p1;
    }
};



// 剑指offer - 链表中环的入口节点
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head, *fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        // 慢指针从头开始走, 再次和fast指针相遇点即为环的入口节点
        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};


// 剑指offer - 删除链表的倒数第K个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 为了防止删除头结点, 这里需要定义一个虚拟头结点, 其后链接head节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        // 单链表中删除一个节点的前提是知道其前一个节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        // 定义两个指针
        ListNode* p1 = head, *p2 = head;

        // p1先走K步(此时p1再走n-k步就走尾)
        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        // p2从头开始和p1一起走, 当p1指向空时, p2所在的位置即为答案
        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 剑指offer - 两个链表的第一个公共节点
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先遍历链表A然后遍历链表B, p2先遍历链表B再遍历链表A
        // 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA, *p2 = headB;

        while(p1 != p2)
        {
            if(p1 == nullptr)
                p1 = headB;
            else
                p1 = p1->next;

            if(p2 == nullptr)
                p2 = headA;
            else
                p2 = p2->next;
        }

        return p1;
    }
};



// 剑指offer - 合并两个排序的链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;
        ListNode* p1 = l1, *p2 = l2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};


// 合并K个排序链表 - 较难
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        if(lists.empty())
            return nullptr;

        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            p->next = pMin;

            p = p->next;

            if(pMin->next)
                pq.push(pMin->next);
        }

        return newnode->next;
    }
};



// 分隔链表
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // 定义两个虚拟头结点
        // 将原链表分成两条短链表, 一者节点值小于x, 一者节点值不小于x
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;

        ListNode* p = head;

        while(p != nullptr)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }

            p = p->next;
        }

        // 节点值不小于x的短链表尾置空
        p2->next = nullptr;

        p1->next = newnode2->next;
        return newnode1->next;
    }
};



// 剑指offer - 合并两个排序的链表
 class Solution {
  453 public:
  454     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
  455     {
  456         // 定义一个虚拟头结点
  457         ListNode* newnode = new ListNode(-1), *p = newnode;
  458         ListNode* p1 = l1, *p2 = l2;
  459 
  460         while(p1 && p2)
  461         {                                                                                                                                              
  462             if(p1->val < p2->val)
  463             {
  464                 p->next = p1;
  465                 p1 = p1->next;
  466             }
  467             else
  468             {
  469                 p->next = p2;
  470                 p2 = p2->next;
  471             }
  472 
  473             p = p->next;
  474         }
  475 
  476         if(p1)
  477             p->next = p1;
  478 
  479         if(p2)
  480             p->next = p2;
  481 
  482         return newnode->next;
  483     }

  };



class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        if(lists.empty())
            return nullptr;

        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            p->next = pMin;

            p = p->next;

            if(pMin->next)
                pq.push(pMin->next);
        }

        return newnode->next;
    }
};


// 
// 链表的倒数第K个节点
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k ; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 剑指offer - 合并排序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;
        // 定义一个最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }
        
        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);
            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};



// 剑指offer - 两个链表的第一个交点
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        // 定义两个指针p1和p2, p1先遍历链表A再遍历链表B, p2先遍历链表B再遍历链表A, 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA, *p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }

        return p1;
    }
};



// 剑指offer - 环形链表II
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {

        // 定义快慢指针
        ListNode* slow = head, *fast = head;

        // 判断是否有环
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }

        // 如果是因为循环结束退出则无环
        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};



// 剑指offer - 删除链表的倒数第K个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 防止删除头结点, 所以定义一个虚拟节点并且指向头结点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        // 单链表中删除一个节点需要先找到该节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    // 找到倒数第K个节点
    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};



// 剑指offer - 两个链表的第一个公共节点
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先遍历链表A再遍历链表B, p2先遍历链表B再遍历链表A, 这样就保证了遍历链表的长度相同
        ListNode* p1 = headA, *p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }    

        return p1;

    }
};


// 剑指offer - 合并两个有序链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        // 定义虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = l1, *p2 = l2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};



// 剑指offer - 链表的倒数第K个节点
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1 != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};



// 环形链表
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                return true;
        }

        return false;
    }
};


// 环形链表
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                return true;
        }   

        return false;
    }
};


// 环形链表II
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};

// 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先指向链表A再指向链表B， p2先指向链表B再指向链表A， 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }

        return p1;
    }
};

// 删除链表的倒数第K个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 单链表中删除一个节点需要找到该节点的前一个节点
        // 为了避免删除头节点，这里定义一个虚拟头节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head;
        ListNode* p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }

};


// 合并两个有序链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        // 定义一个虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;
        ListNode* p1 = list1, *p2 = list2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next =  p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;

    }
};


// 合并K个链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        // 定义一个虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;
        ListNode* p1 = list1, *p2 = list2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next =  p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;

    }
};


// 剑指offer - 合并K个链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);
            
            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};

/ 分隔链表
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // 定义两个虚拟头结点
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;
        ListNode* p = head;

        while(p != nullptr)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }
            p = p->next;
        }
        
        p2->next = nullptr;
        p1->next = newnode2->next;

        return newnode1->next;
    }
};



// 合并K个链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);
            
            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};


// 环形链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);
            
            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
};


class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                return true;
        }    

        return false;
    }
};



// 环形链表II
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }    

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};

// 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先指向链表A再指向链表B， p2先指向链表B再指向链表A， 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }    

        return p1;
    }
};


// 删除链表的倒数第N个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 为避免删除链表的头节点， 我们需要定义一个虚拟头节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head; // 千万别忘记 - 易忘

        // 单链表中删除一个节点的前提是找到其前一个节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        // 定义两个指针p1和p2
        ListNode* p1 = head;
        ListNode* p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1 != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 合并两个有序链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        // 定义一个虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = list1, *p2 = list2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }    

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};


// 合并K个升序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);

            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};


// 分割链表
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // 定义两个虚拟头节点
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;
        ListNode* p = head;
        
        while(p != nullptr)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }
            
            p = p->next;
        }

        p2->next = nullptr;
        p1->next = newnode2->next;

        return newnode1->next;

    }
};


// 链表的中间节点
class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};


// 剑指offer - 链表中倒数第K个节点
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        // 定义两个指针p1和p2
        ListNode* p1 = head;
        ListNode* p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1 != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;

    }
};


// 剑指offer - 合并两个排序的链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        // 定义虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = l1, *p2 = l2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};


// 剑指offer - 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先指向链表A再指向链表B， p2先指向链表B再指向链表A， 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }

        return p1;
    }
};


// 剑指offer - 删除链表的倒数第N个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 为避免删除头节点， 我们需要定义一个虚拟头节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head; // 容易忘记这步操作

        // 单链表中删除一个节点的前提是找到其前一个节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head;
        ListNode* p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1 != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 剑指offer - 环的入口节点
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;   
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }   

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};


// 剑指offer - 两个链表的第一个重合节点
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先指向链表A再指向链表B， p2先指向链表B再指向链表A， 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else    
                p2 = headA;
        }

        return p1;
    }
};


// 剑指offer - 合并排序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);

            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};


// 剑指offer - 合并排序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b){return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);

            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};

// 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针，p1先指向链表A再指向链表B，p2先指向链表B再指向链表A
        // 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else    
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else    
                p2 = headA;
        }    

        return p1;
    }
};


// 剑指offer - 链表中环的入口节点
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head, *fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }    

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};


// 剑指offer - 删除链表的倒数第n个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 为避免删除头节点，需要定义一个虚拟头节点，并连接到头节点之前
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        // 单链表中删除一个节点需要找到其前一个节点的地址
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head;
        ListNode* p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 剑指offer - 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针,p1先指向链表A再指向链表B，p2先指向链表B再指向链表A
        // 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }    

        return p1;
    }
};


// 剑指offer - 合并两个排序的链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        // 定义虚拟节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = l1, *p2 = l2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};


// 剑指offer - 链表中倒数第k个节点
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 分割链表
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // 定义两个虚拟节点
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;
        ListNode* p = head;
        
        while(p)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }

            p = p->next;
        }

        p2->next = nullptr;
        p1->next = newnode2->next;

        return newnode1->next;
    }
};


// 删除排序链表中的重复元素
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if(head == nullptr)
            return nullptr;

        ListNode* slow = head, *fast = head;

        while(fast != nullptr)
        {
            if(fast->val != slow->val)
            {
                slow->next = fast;
                slow = slow->next;
            }

            fast = fast->next;
        }

        slow->next = nullptr;

        return head;
    }
};


// 剑指offer - 合并排序链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto& head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            p->next = pMin;
            p = p->next;
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);
        }

        return newnode->next;
    }
};


// 合并K个链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto& head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            p->next = pMin;
            p = p->next;
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);
        }

        return newnode->next;
    }
};


// 剑指offer - 相交链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先指向链表A再指向链表B，p2先指向链表B再指向链表A， 这样保证了遍历链表的长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }    

        return p1;
    }
};


// 剑指offer - 链表中环的入口节点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* slow = head, *fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }    

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};


// 剑指offer - 删除链表的倒数第n个节点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 为防止删除头节点，定义一个虚拟节点，并头插到头节点之前
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        // 单链表中删除一个节点的前提是知道该节点的前一个节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 剑指offer - 相交链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else 
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }    

        return p1;
    }
};



// 剑指offer - 合并两个排序的链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = l1, *p2 = l2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};



// 剑指offer - 链表中倒数第k个节点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 剑指offer - 合并排序链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto& head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            p->next = pMin;
            p = p->next;
            pq.pop();

            if(pMin->next)
                pq.push(pMin->next);
        }

        return newnode->next;
    }
};



// 剑指offer - 相交链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        ListNode* p1 = headA, *p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else 
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }    

        return p1;
    }
};



// 剑指offer - 链表中环的入口节点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* slow = head, *fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};



// 剑指offer - 删除链表的倒数第n个节点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 为防止删除头节点，定义一个虚拟节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        // 单链表中删除一个节点，需要先找到该节点的前一个节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};



// 剑指offer - 相交链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 !=  p2)
        {
            if(p1)
                p1 = p1->next;
            else 
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }    

        return p1;
    }
};



// 剑指offer - 合并连个排序的链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = l1, *p2 = l2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};



// 分隔链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;

        ListNode* p = head;

        while(p != nullptr)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }

            p = p->next;
        }

        p2->next = nullptr;
        p1->next = newnode2->next;

        return newnode1->next;
    }
};



// 反转链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr)
            return head;

        ListNode* last = reverseList(head->next);

        head->next->next = head;

        head->next = nullptr;

        return last;
    }
};



// 反转链表 - 递归版本
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        // 1->2->3->N
        if(head == nullptr || head->next == nullptr)
            return head;

        ListNode* last = reverseList(head->next); // 1->2<-3

        head->next->next = head; // 1<-2<-3

        head->next = nullptr; // N<-1<-2<-3

        return last;
    }
};



// 反转链表前N个节点
ListNode* successor = nullptr;

// 反转以 head 为起点的前N个节点，返回新的头节点
ListNode* reverseN(ListNode* head, int n)
{
	if(n == 1)
	{
		successor = head->next;
		return head;
	}

	ListNode* last = reverseN(head->next, n - 1);
	head->next->next = head;
	head->next = successor;

	return last;
}

// 反转链表的前N个节点

ListNode* successor = nullptr;

// 反转以 head 为起点的前N个节点，返回新的头节点
ListNode* reserveN(ListNode* head, int n)
{
	if(n == 1)
	{
		successor = head->next;
		return head;
	}
	
	listNode* last = reserveN(head->next);
	head->next->next = head;
	head->next = successor;

	return last;
}


// 反转链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        // base case 
        if(head == nullptr || head->next == nullptr)
            return head;

        ListNode* last = reverseList(head->next);

        head->next->next = head;
        head->next = nullptr;

        return last; 
    }
};



// 剑指offer - 反转链表 （这道题不知道为什么使用C++版本的递归不行，但是换成C语言又可以了）
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head)
{
    // base case 
    if(head == NULL || head->next == NULL)
        return head;

    struct ListNode* last = reverseList(head->next);

    head->next->next = head;
    head->next = NULL;

    return last;
}



// 反转整个链表
ListNode* reverse(ListNode* head)
{
	// base case
	if(head == nullptr || head->next == nullptr)
		return head;

	ListNode* last = reverse(head->next);
	head->next->next = head;
	head->next = nullptr;

	return last;
}


// 反转链表前N个节点

ListNode* successor = nullptr;

ListNode* reverseN(ListNode* head, int n)
{
	if(n == 1)
	{
		successor = head->next;
		return head;
	}

	ListNode* last = reverseN(head->next, n - 1);
	head->next->next = head;
	head->next = successor;

	return last;
}


// 反转链表II - 较难
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) 
    {
        // base case
        if(left == 1)
        {
            return reverseN(head, right);
        }

        head->next = reverseBetween(head->next, left - 1, right - 1);

        return head;
    }

private:
    ListNode* successor = nullptr;

    ListNode* reverseN(ListNode* head, int n)
    {
        // base case
        if(n == 1)
        {
            successor = head->next;
            return head;
        }

        ListNode* last = reverseN(head->next, n - 1);
        head->next->next = head;
        head->next = successor;

        return last;
    }
};


// 反转链表II
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) 
    {
        // base case
        if(left == 1) // 反转链表的前N个节点
        {
            return reverseN(head, right);
        }

        head->next = reverseBetween(head->next, left-1, right-1);

        return head;
    }

private:
    ListNode* successor = nullptr;

    ListNode* reverseN(ListNode* head, int n)
    {
        // base case
        if(n == 1)
        {
            successor = head->next;
            return head;
        }

        ListNode* last = reverseN(head->next, n - 1);
        head->next->next = head;
        head->next = successor;

        return last;
    }
};


// 剑指offer - 反转链表 - 迭代版
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* nxt = head;

        while(cur != nullptr)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};


// K个一组反转链表
ListNode* reverseKGroup(ListNode* head, int k)
{
	if(head == nullptr) return nullptr;

	// 区间 [a, b} 包含K个待反转元素
	ListNode* a = head, *b = head;

	for(int i = 0; i < k; i++)
	{
		// 不足k个，不需要反转
		if(b == nullptr) return head;

		b = b->next;
	}

	// 反转前K个元素
	ListNode* newHead = reverse(a, b);
	// 递归反转后续链表并连接起来
	a->next = reverseKGroup(b, k);

	return newHead;

}

 
// K个一组反转链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        if(head == nullptr) return nullptr;

        ListNode* a = head, *b = head;

        for(int i = 0; i < k; i++)
        {
            if(b == nullptr) return head;
            b = b->next;
        }

        ListNode* newHead = reverse(a, b);
        a->next = reverseKGroup(b, k);

        return newHead;
    }

    ListNode* reverse(ListNode* a, ListNode* b)
    {
        ListNode* pre = nullptr;
        ListNode* cur = a, *nxt = a;

        while(cur != b)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;            
        }

        return pre;
    }
};



// 力扣热题100 - K个一组反转链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        if(head == nullptr) return nullptr;

        ListNode* a = head, *b = head;

        for(int i = 0; i < k; i++)
        {
            // 不足K个，直接返回
            if(b == nullptr) return head;
            b = b->next;
        }

        ListNode* newHead = reverse(a, b);
        a->next = reverseKGroup(b, k);

        return newHead;
    }

    ListNode* reverse(ListNode* a, ListNode* b)
    {
        ListNode* pre = nullptr;
        ListNode* cur = a, *nxt = a;

        while(cur != b)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};



// 反转链表 - 递归解法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        // base case
        if(head == nullptr || head->next == nullptr)
            return head;

        ListNode* last = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return last;
    }
};


// 反转链表 - 迭代版本
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* pre = nullptr;
        ListNode* cur = head, *nxt = head;

        while(cur != nullptr)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};


// 反转链表II - 递归
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) 
    {
        if(left == 1)
        {
            return reverseN(head, right); // 变成了 反转链表前N个节点
        }

        head->next = reverseBetween(head->next, left - 1, right - 1);

        return head;
    }

private:
    ListNode* successor = nullptr;

    ListNode* reverseN(ListNode* head, int n)
    {
        if(n == 1)
        {
            successor = head->next;
            return head;
        }

        ListNode* last = reverseN(head->next, n - 1);
        head->next->next = head;
        head->next = successor;

        return last;
    }
};


// 反转链表II
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) 
    {
        // base case
        if(left == 1)
            return reverseN(head, right); // 变成了 反转链表前N个节点
            
        head->next = reverseBetween(head->next, left-1, right-1);

        return head;
    }

private:
    ListNode* successor = nullptr;

    ListNode* reverseN(ListNode* head, int n)
    {
        // base case
        if(n == 1)
        {
            successor = head->next;
            return head;
        }

        ListNode* last = reverseN(head->next, n-1);
        head->next->next = head;
        head->next = successor;

        return last;
    }
};



// K个一组反转链表 - 较难
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        if(head == nullptr) return nullptr;

        ListNode* a = head, *b = head;

        for(int i = 0; i < k; i++)
        {
            // 不足K个节点，直接返回
            if(b == nullptr) return head;

            b = b->next;
        }

        // 反转前K个节点
        ListNode* newHead = reverse(a, b);
        // 递归反转后续节点
        a->next = reverseKGroup(b, k);

        return newHead;
    }

    ListNode* reverse(ListNode* a, ListNode* b)
    {
        ListNode* pre = nullptr;
        ListNode* cur = a, *nxt = a;

        while(cur != b)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};


// 两两交换链表的中点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        // base case
        if(head == nullptr || head->next == nullptr)
            return head;

        ListNode* a = head, *b = head;

        for(int i = 0; i < 2; i++)
        {
            if(b == nullptr) return head;

            b = b->next; 
        }

        // 反转前2个节点
        ListNode* newHead = reverse(a, b);

        // 递归反转后续节点
        a->next = swapPairs(b);

        return newHead;
    }

    ListNode* reverse(ListNode* a, ListNode* b)
    {
        ListNode* pre = nullptr;
        ListNode* cur = a, *nxt = a;

        while(cur != b)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};



// 两两交换链表的节点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        // base case
        if(head == nullptr || head->next == nullptr)
            return head; 

        ListNode* first = head;
        ListNode* second = head->next;
        ListNode* third = head->next->next;

        // 反转前两个节点
        second->next = first;

        // 递归交换后续节点
        first->next = swapPairs(third);

        return second;
    }
};


// 回文链表 - 注意对于细节的处理
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) 
    {
        ListNode* slow = head, *fast = head;

        // 先找到链表的中间节点
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 偶数个节点时，slow还需要多走一步
        if(fast != nullptr)
            slow = slow->next;

        // 此时slow就是中间节点
        // 然后反转后半部分节点, 再进行遍历比较
        ListNode* tail = reverse(slow);

        while(tail != nullptr)
        {
            if(head->val != tail->val)
            {
                return false;
            }
            else
            {
                head = head->next;
                tail = tail->next;
            }
        }

        return true;
    }

    ListNode* reverse(ListNode* head)
    {
        ListNode* pre = nullptr;
        ListNode* cur = head, *nxt = head;

        while(cur)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) 
    {
        ListNode* slow = head, *fast = head;

        // 先找到中间节点
        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 注意对于偶数个节点的处理，slow需要多走一步
        if(fast != nullptr) // 偶数节点时
            slow = slow->next;

        // 然后反转后半部分节点即可
        ListNode* tail = reverse(slow);

        while(tail != nullptr)
        {
            if(head->val != tail->val)
            {
                return false;
            }
            else
            {
                head = head->next;
                tail = tail->next;
            }
        }

        return true;
    }

    ListNode* reverse(ListNode* head)
    {
        ListNode* pre = nullptr;
        ListNode* cur = head, *nxt = head;

        while(cur != nullptr)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) 
    {
        ListNode* slow = head, *fast = head;

        // 先找到中间节点
        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 注意对于偶数个节点的处理，slow需要多走一步
        if(fast != nullptr) // 偶数节点时
            slow = slow->next;

        // 然后反转后半部分节点即可
        ListNode* tail = reverse(slow);

        while(tail != nullptr)
        {
            if(head->val != tail->val)
            {
                return false;
            }
            else
            {
                head = head->next;
                tail = tail->next;
            }
        }

        return true;
    }

    ListNode* reverse(ListNode* head)
    {
        ListNode* pre = nullptr;
        ListNode* cur = head, *nxt = head;

        while(cur != nullptr)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};



// 反转链表 - 递归解法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        // base case 
        if(head == nullptr || head->next == nullptr)
            return head;

        ListNode* last = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return last;
    }
};



// 反转链表 - 迭代解法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* pre = nullptr;
        ListNode* cur = head, *nxt = head;

        while(cur != nullptr)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};



// 反转链表II
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) 
    {
        // base case
        if(left == 1)
        {
            return reverseN(head, right);
        }

        head->next = reverseBetween(head->next, left - 1, right - 1);

        return head;
    }

private:
    ListNode* successor = nullptr;

    ListNode* reverseN(ListNode* head, int n)
    {
        // base case
        if(n == 1)
        {
            successor = head->next;
            return head;
        }

        ListNode* last = reverseN(head->next, n - 1);
        head->next->next = head;
        head->next = successor;

        return last;
    }
};


// 反转链表II
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) 
    {
        // base case
        if(left == 1)
        {
            return reverseN(head, right);
        }

        head->next = reverseBetween(head->next, left - 1, right - 1);

        return head; 
    }

private:
    ListNode* successor = nullptr;

    ListNode* reverseN(ListNode* head, int n)
    {
        // base case
        if(n == 1)
        {
            successor = head->next;
            return head;
        }

        ListNode* last = reverseN(head->next, n - 1);
        head->next->next = head;
        head->next = successor;

        return last;
    }

};


// K个一组反转链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        if(head == nullptr) return nullptr;

        ListNode* a = head, *b = head;

        for(int i = 0; i < k; i++)
        {
            if(b == nullptr) return head; // 不足K个， 直接返回

                b = b->next;
        }

        // 先反转前K个节点
        ListNode* newHead = reverse(a, b);

        // 再递归反转后续节点
        a->next = reverseKGroup(b, k);

        return newHead;
    }

    ListNode* reverse(ListNode* a, ListNode* b)
    {
        ListNode* pre = nullptr;
        ListNode* cur = a, *nxt = a;

        while(cur != b)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};


// 两两交换链表的节点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        if(head == nullptr) return nullptr;

        ListNode* a = head, *b = head;

        for(int i = 0; i < 2; i++)
        {
            if(b == nullptr) return head; // 不足2个节点，直接返回

            b = b->next;
        }

        // 反转前2个节点
        ListNode* newHead = reverse(a, b);

        // 递归反转后续节点
        a->next = swapPairs(b);

        return newHead;
    }

    ListNode* reverse(ListNode* a, ListNode* b)
    {
        ListNode* pre = nullptr;
        ListNode* cur = a, *nxt = a;

        while(cur != b)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};


// 两两交换链表的节点 - 理解版
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        // base case
        if(head == nullptr || head->next == nullptr)
            return head;

        ListNode* first = head;
        ListNode* second = head->next;
        ListNode* third = head->next->next;

        // 反转前两个节点
        second->next = first;

        // 递归反转后续节点
        first->next = swapPairs(third);

        return second;
    }
};



// 回文链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) 
    {
        ListNode* slow = head, *fast = head;

        // 先找到链表的中间节点
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        if(fast != nullptr)// 奇数时的情况
            slow = slow->next; // slow多走一步

        // 反转链表后半部分
        ListNode* tail = reverse(slow);

        while(tail != nullptr)
        {
            if(tail->val != head->val)
                return false;

            tail = tail->next;
            head = head->next;
        }

        return true;
    }


    ListNode* reverse(ListNode* head)
    {
        if(head == nullptr || head->next == nullptr)
            return head;

        ListNode* last = reverse(head->next);
        head->next->next = head;
        head->next = nullptr;

        return last;
    }
};


// 相交链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else 
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else 
                p2 = headA;
        }    

        return p1;
    }
};



// 环形链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        ListNode* slow = head, *fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                return true;
        }    

        return false;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }    

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = list1, *p2 = list2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }    

        if(p1)
        {
            p->next = p1;
        }

        if(p2)
        {
            p->next = p2;
        }

        return newnode->next;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* p1 = l1, *p2 = l2;

        ListNode* newnode = new ListNode(-1);

        ListNode* p = newnode;

        int carry = 0; //记录进位

        // 只有链表都走到最后了 以及 没有进位，循环才结束
        while(p1 != nullptr || p2 != nullptr || carry > 0)
        {
            int val = carry;

            if(p1 != nullptr)
            {
                val += p1->val;
                p1 = p1->next;
            }

            if(p2 != nullptr)
            {
                val += p2->val;
                p2 = p2->next;
            }

            // 处理进位的情况
            carry = val / 10;
            val = val % 10;

            // 构建新节点
            ListNode* node = new ListNode(val);

            p->next = node;

            p = p->next;
        }

        return newnode->next;
    }
};



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* newnode = new ListNode(-1);
        ListNode* p = newnode;
        ListNode* p1 = l1, *p2 = l2;

        int carry = 0; // 记录进位

        while(p1 != nullptr || p2!= nullptr || carry > 0)
        {
            int val = carry;

            if(p1 != nullptr)
            {
                val += p1->val;
                p1 = p1->next;
            }

            if(p2 != nullptr)
            {
                val += p2->val;
                p2 = p2->next;
            }

            // 控制进位
            carry = val / 10;
            val = val % 10;

            p->next = new ListNode(val);
            p = p->next;
        }

        return newnode->next;
    }
};



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) 
    {
        if(head == nullptr)
            return {};

        // 把子链表反着打印出来
        vector<int> subList = reversePrint(head->next);

        subList.push_back(head->val);

        return subList;
    }
};


class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
        // dp函数的定义：从第一行开始下降(matrix[0][..])，落到matrix[i[j]]的最小路径和为dp(matrix, i, j)

        int n = matrix.size();

        // 建立备忘录
        vector<vector<int>> memo(n, vector<int>(n, 66666)); // 最大路径和也就是10000， 只要大于10000均可
        
        int res = INT_MAX;

        for(int j = 0; j < n; j++)
        {
            // 答案一定在matrix[n-1][..]
            res = min(res, dp(matrix, memo, n - 1, j));
        }

        return res;
    }

    int dp(vector<vector<int>>& matrix, vector<vector<int>>& memo, int row, int col)
    {
        if(row < 0 || col < 0 || row >= matrix.size() || col >= matrix[0].size())
            return 99999; // 越界

        // base case
        if(row == 0)
            return matrix[0][col];

        if(memo[row][col] != 66666)
            return memo[row][col];

        memo[row][col] = matrix[row][col] + threeMin(
            dp(matrix, memo, row - 1, col),
            dp(matrix, memo, row - 1, col - 1),
            dp(matrix, memo, row - 1, col + 1)
        );

        return memo[row][col];
    }

    int threeMin(int first, int second, int third)
    {
        return min(first, min(second, third));
    }

};


class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
        // dp函数的定义：从第一行(matrix[0][..])开始到matrix[i][j]的最小路径和为dp(matrix,i,j)
        int n = matrix.size();

        vector<vector<int>> memo(n, vector<int>(n, 66666)); // 最大路径和不可能超过10000
        int res = INT_MAX;

        for(int j = 0; j < n; j++)
        {
            // 答案一定在dp(matrix, n - 1, ..)中
            res = min(res, dp(matrix, memo, n - 1, j));
        }

        return res;
    }

    int dp(vector<vector<int>>& matrix, vector<vector<int>>& memo, int row, int col)
    {
        // 检查索引
        if(row < 0 || col < 0 || row >= matrix.size() || col >= matrix[0].size())
            return 99999;
        
        // base case
        if(row == 0)
            return matrix[0][col];

        // 检查备忘录
        if(memo[row][col] != 66666)
            return memo[row][col];

        // 进行状态转移
        memo[row][col] = matrix[row][col] + threeMin(
            dp(matrix, memo, row - 1, col),
            dp(matrix, memo, row - 1, col - 1),
            dp(matrix, memo, row - 1, col + 1)
        );

        return memo[row][col];
    }

    int threeMin(int first, int second, int third)
    {
        return min(first, min(second, third));
    }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    Node* cloneTree(Node* root) 
    {
        if(root == nullptr)
            return nullptr;

        // 先拷贝根节点
        Node* cpRoot = new Node(root->val);

        // 再拷贝根节点的所有孩子节点
        for(Node* child : root->children)
        {
            cpRoot->children.push_back(cloneTree(child));
        }    

        return cpRoot;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) 
    {
        // 首先找到该节点的前一个节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        ListNode* prev = findValPrevNode(newnode, val);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findValPrevNode(ListNode* head, int val)
    {
        ListNode* cur = head;
        ListNode* prev = nullptr;

        while(cur != nullptr)
        {
            if(cur->val != val)
            {
                prev = cur;
                cur = cur->next;
            }
            else 
            {
                return prev;
            }
        }

        return nullptr;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        ListNode* a = head, *b = head;

        for(int i = 0; i < k; i++)
        {
            if(nullptr == b)
            {
                return head;
            }

            b = b->next;
        }

        ListNode* newHead = reverse(a, b);
        head->next = reverseKGroup(b, k);

        return newHead;
    }

    ListNode* reverse(ListNode* a, ListNode* b)
    {
        ListNode* prev = nullptr;
        ListNode* cur = a, *next = a;

        while(cur != b)
        {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }
};

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1;

        while(left <= right)
        {
            int mid = left + (right - left) / 2;

            if(nums[mid] == target)
            {
                return mid;
            }

            if(nums[mid] >= nums[left])
            {
                // mid落在断崖的左边
                if(target >= nums[left] && target < nums[mid])
                {
                    // 说明此时target落在[left, mid-1]上
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            else
            {
                // mid落在断崖的右边
                if(target <= nums[right] && target > nums[mid])
                {
                    // 说明此时target落在[mid + 1, right]上
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
};


class Solution {
public:
    string minWindow(string s, string t) 
    {
        int left = 0, right = 0;
        // 记录需要凑齐的字符及其出现次数
        unordered_map<char, int> need;
        for(char c : t)
        {
            need[c]++;
        }

        // 记录窗口中字符及其出现次数
        unordered_map<char, int> window;

        int vaild = 0;
        // 记录最小覆盖子串的起始位置以及长度
        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            char c = s[right];
            right++;

            if(need.count(c))
            {
                window[c]++;

                if(need[c] == window[c])
                    vaild++;
            }

            // 判断何时缩小窗口
            while(vaild == need.size())
            {
                // 更新最小覆盖子串
                if(len > right - left)
                {
                    start = left;
                    len = right - left;
                }

                char d = s[left];
                left++;

                if(need.count(d))
                {
                    if(need[d] == window[d])
                        vaild--;

                    window[d]--;
                }
            }
        }
        
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        // 先对数组进行排序
        sort(nums.begin(), nums.end());

        return nSum(nums, 3, 0, 0);
    }

    vector<vector<int>> nSum(vector<int>& nums, int n, int start, int target)
    {
        int sz = nums.size();

        vector<vector<int>> res;

        if(n < 2 || sz < n)
        {
            return res;
        }

        if(n == 2)
        {
            int left = start, right = sz - 1;

            while(left < right)
            {
                int sum = nums[left] + nums[right];
                int leftNum = nums[left], rightNum = nums[right];

                if(sum == target)
                {
                    res.push_back({leftNum, rightNum});

                    while(left < right && leftNum == nums[left])
                        left++;
                    while(left < right && rightNum == nums[right])
                        right--;
                }
                else if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {
                    right--;
                }
            }
        }
        else
        {
            // n > 2
            for(int i = start; i < sz; i++)
            {
                vector<vector<int>> twoNums = nSum(nums, n - 1, i + 1, target - nums[i]);

                for(vector<int> twoNum : twoNums)
                {
                    twoNum.push_back(nums[i]);
                    res.push_back(twoNum);
                }

                // 防止第一个数重复
                while(i < sz - 1 && nums[i] == nums[i+1])
                {
                    i++;
                }
            }
        }

        return res;
    }

};


class Solution {
public:

    vector<string> res; // 记录结果
    vector<string> track; // 记录递归遍历路径

    vector<string> restoreIpAddresses(string s) 
    {
        backtrack(s, 0);

        return res;
    }

    void backtrack(string& s, int start)
    {
        // 结束条件
        if(start == s.size() && track.size() == 4)
        {
            res.push_back(join(track));
            return;
        }

        for(int i = start; i < s.size(); i++)
        {
            // 选择列表
            // 判断s[start,i]是不是合法的Ip
            if(!isVaild(s, start, i))
            {
                continue;
            }

            track.push_back(s.substr(start, i - start + 1));

            backtrack(s, i + 1);

            track.pop_back();
        }
    }

    string join(vector<string>& track)
    {
        string res;

        for(int i = 0; i < track.size(); i++)
        {
            res += track[i];

            if(i < track.size() - 1)
            {
                res += '.';
            }
        }

        return res;
    }

    bool isVaild(string& s, int start, int end)
    {
        int len = end - start + 1;

        if(len > 3 || len == 0)
        {
            return false;
        }

        if(len > 1 && s[start] == '0')
        {
            return false;
        }

        if(stoi(s.substr(start, len)) > 255)
        {
            return false;
        }

        return true;
    }
};


class Solution {
public:
    int firstMissingPositive(vector<int>& nums) 
    {
        int n = nums.size();

        // 遍历数组，将非正整数的元素忽略，即是映射到n之外
        for(int i = 0; i < n; i++)
        {
            if(nums[i] <= 0)
            {
                nums[i] = n + 1;
            }
        }

        // 遍历数组中的元素，将以该元素为下标的值按照绝对值取反
        for(int i = 0; i < n; i++)
        {
            if(abs(nums[i]) <= n)
            {
                nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1]);
            }
        }

        for(int i = 0; i < n; i++)
        {
            if(nums[i] > 0)
            {
                return i + 1;
            }
        }

        return n + 1;
    }
};

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) 
    {   
        int n = nums.size();

        // 将数组中的非正整数元素忽略，即是映射到n之外
        for(int i = 0; i < n; i++)
        {
            if(nums[i] <= 0)
            {
                nums[i] = n + 1;
            }
        }

        // 遍历数组中的元素，将以元素的值为对应的下标里的元素取其绝对值的相反数，也就是做标记
        for(int i = 0; i < n; i++)
        {
            if(abs(nums[i]) <= n) // 说明是正整数
            {
                nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1]);
            }
        }

        // 遍历数组中的元素，元素值不为负数的就是答案
        for(int i = 0; i < n; i++)
        {
            if(nums[i] > 0)
            {
                return i + 1;
            }
        }

        return n + 1;
    }
};




// 题目：
// 给定一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数，并构造测试数据进行测试

// 数据范围:
// -231<=nums<=231-1
// 0<=len(nums)<=5*105

// 数组举例：
// 输入：
// [1,0,2]
// 返回值：
// 3

// 示例2
// 输入：
// [-2,3,4,1,5]
// 返回值：
// 2


#include <iostream>
#include <vector>

using namespace std;

int getMin(vector<int>& nums)
{
    int n = nums.size();

    // 遍历数组忽略非正整数，也就是将其映射到n之外
    for(int i = 0; i < n; i++)
    {
        if(nums[i] <= 0)
            nums[i] = n + 1;
    }

    // 遍历数组中的元素，将以该元素值为下标的元素，将其值置换为其绝对值得相反数
    for(int i = 0; i < n; i++)
    {
        if(abs(nums[i]) <= n) // 也就是正整数
        {
            nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1]); // 做标记
        }
    }

    // 遍历数组找到不为负数的值，其下标就是所求
    for(int i = 0; i < n; i++)
    {
        if(nums[i] > 0)
        {
            return i + 1;
        }
    }

    return n + 1;


}

int main()
{
    vector<int> nums;
    int num = 0;

    while(cin >> num)
    {
        nums.push_back(num);

        if(cin.get() == '\n')
        {
            break;
        }
    }

    cout << getMin(nums) << endl;

    return 0;
}

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) 
    {
        // 记录原始节点到克隆节点的映射
        unordered_map<Node*, Node*> nodeToClone;

        // 第一次遍历，生成克隆节点
        for(Node* p = head; p != nullptr; p = p->next)
        {
            if(nodeToClone.find(p) == nodeToClone.end())
            {
                nodeToClone[p] = new Node(p->val);
            }
        }

        // 第二次遍历，将克隆节点连接起来
        for(Node* p = head; p != nullptr; p = p->next)
        {
            // 普通节点
            if(p->next != nullptr)
                nodeToClone[p]->next = nodeToClone[p->next];

            // 随机节点
            if(p->random != nullptr)
                nodeToClone[p]->random = nodeToClone[p->random];
        }

        return nodeToClone[head];
    }
};



